This invention relates to a secret sharing system and a storage medium for a crypto system based on the problem of factorization into prime factors, and more particularly to a crypto system and a storage device which shares a secret key secretly to n shareholders and enable t of the n shareholders to perform shared decryption and signature without computing the secret key.
One known crypto system based on the problem of factorization into prime factors is a secret sharing scheme called a threshold scheme in the field of secret sharing using, for example, an RSA crypto system. The threshold scheme has a secret information recovery characteristic with a threshold of t as a boundary line. The secret information recovery characteristic is such that, when secret information is shared into n share, the secret information is recovered completely from t out of the n share but cannot be recovered at all from txe2x88x921 share (where 1 less than t less than n).
One known secret sharing scheme of this type is a (t, n) secret sharing scheme where the concept of the threshold scheme has been introduced into the RSA crypto system and a secret key has been shared secretly in the (t, n) type (Y. Frankel, P. Gemmell, P. D.
MacKenzie and M. Yung, xe2x80x9cOptimal-resilience proactive public-key cryptosystems,xe2x80x9d 38th Annual Symposium on Foundations of Computer Science, pp. 384-393, 1997, which is hereinafter referred to as reference [FGMY97]), and T. Okamoto, xe2x80x9cThreshold key-recovery systems for RSA,xe2x80x9d Security Protocols, LNCS 1361, pp. 191-200, 1997, which is hereinafter referred as reference [Oka97]).
Reference [FGMY97] has described a method of enabling any t shareholders to perform decryption and signature without computing a secret key d in an environment where dealers (distributors) exist. That is, it is a method of enabling a secret key d capable of decryption and signature to be created from any t share even if shareholders do not know prime factors of composite number N.
On the other hand, in an environment where no dealer exists, one known secret sharing scheme is a (n, n) secret sharing scheme, not a threshold scheme. In the (n, n) secret sharing scheme, all the shareholders create a key where nobody knows the secret(D. Boneh and M. Franklin, xe2x80x9cEfficient generation of shared RSA keys,xe2x80x9d Advances in Cryptology-CRYPTO ""97, LNCS 1294, pp. 425-439, 1997, which is hereinafter referred to as reference [BF97]).
In the scheme of reference [BF97], when a key is generated, (n, n) secret sharing is performed simultaneously. In addition, by combining the partial outputs from all the shareholders using the held share, the ciphertext can be decrypted without computing the secret key d.
In reference [BF97], a method of constructing (2, n) secret sharing (nxe2x89xa73) from (2, 2) secret sharing has been described as shown in the following algorithm.
To simplify explanation, it is assumed that a user knows a secret key d and the user performs (2, n) secret sharing of the secret key d. It is also assumed that the number of secret sharing polynomials expressing combinations of share is r+1 where r=┌log n┘ for the total number of shareholders P being n (in the present specification, ┌┘ means that the smallest integer equal to or larger than the value in the parentheses).
To perform the (2, 2) secret sharing r+1 times, the user creates r+1 independent polynomials d=d0,0+d0,1=d1,0+d1,1= . . . =dr,0+dr,1 separately.
Next, it is assumed that the identification number of each shareholder in a total of n shareholders is z (z∈[0, n]) and a binary representation of identification number z is z(2)=xcex2rxcex2rxe2x88x921 . . . xcex20. The user takes all the 0-th to n-th shareholders P0 to Pn into account and sends r+1 share {dr, xcex2r, drxe2x88x921, xcex2rxe2x88x921, . . . , d0, xcex20} to the z-th shareholder PZ.
As a result, a set of shares corresponding to a binary representation of identification number z is sent to all the shareholders P0 to Pn.
When the number of an shareholder is set uniquely after the set has been sent, any two shareholders Pi, Pj (ixe2x89xa0j) can recover the secret key d (di,0+di,1=d) from the shares (di,0, di,1) in the same digit differing in bit xcex2 at number z(2) of the r+1 share of (2, 2).
Next, related techniques for expanding the type of secret sharing as the method of constructing the (2, n) secret sharing from the (2, 2) one will be explained.
One of the techniques of this type is a (t, 1m) secret sharing scheme using the (t, 1) type (S. R. Blackburm, M. Burmester, Y. Desmedt and P. R. Wild, xe2x80x9cEfficient multiplicative sharing schemes,xe2x80x9d Advances in Cryptology-EURO-CRYPT ""96, pp. 107-118, 1996, which is hereinafter referred to as reference [BBDW96]). The scheme of reference [BBDW96] is related to 1 that satisfies the following equation (1) for a positive integer m.                                                         1              ≥                                                (                                                                                    t                                                                                                            2                                                                              )                                ⁢                                  (                                      m                    -                    1                                    )                                                                                                                        if                ⁢                                  xe2x80x83                                ⁢                b                            =                                                (                                                                                    t                                                                                                            2                                                                              )                                ⁢                                  (                                      m                    -                    1                                    )                                                                                        (        1        )            
then
t=2 bxe2x89xa71xe2x86x92xe2x89xa71
t=3 bxe2x89xa73xe2x86x921 xe2x89xa73
t=4 bxe2x89xa76xe2x86x921xe2x89xa76
When txe2x89xa74, then t less than 1. Specifically, when txe2x89xa74, it is impossible to construct a (t, n) secret sharing scheme using the (t, t) type.
For this reason, a (3, 32) secret sharing scheme using the (3, 3) type in reference [BBDW96] will be explained hereinafter. Let m=2, 1=3, and t=3, and calculate b using equation (2).                     b        =                                            (                                                                    t                                                                                        2                                                              )                        ⁢                          (                              m                -                1                            )                                =          3                                    (        2        )            
First, (3, 3) secret sharing is performed b+1=4 times and four independent polynomials for the secret key d using equations (3) are formulated:
d=d0,0+d0,1+d0,2 (fist time)=d1,0+d1,1+d1,2 (second time)=d2,0+d2,1+d2,2 (third time)=d3,0+d3,1+d3,2 (fourth time)xe2x80x83xe2x80x83(3)
In addition, let f(x)=a0+a1X (mod 3).
In reference [BBDW96], if a set of the final shareholders (in this case, 32 shareholders) is Pxe2x80x2, f(X) is expressed by equation (4) (the first line on page 113, xe2x80x9cdxe2x80x9d in the equation is replaced with xe2x80x9cmxe2x80x9d, in the present specification).                               f          ⁡                      (            x            )                          =                                            ∑                              i                =                0                                            d                -                1                                      ⁢                                          a                i                            ⁢                              X                i                                              ∈                      P            xe2x80x2                                              (        4        )            
Equation (4), however, is mistaken for the following equation (5).                               f          ⁡                      (            x            )                          =                              ∑                          i              =              0                                      d              -              1                                ⁢                                    a              i                        ⁢                                          X                i                            ⁡                              (                                  mod                  ⁢                                      xe2x80x83                                    ⁢                  l                                )                                                                        (        5        )            
where a0, a1∈F3 and f()=a1.
f1(x)=0 (mod 3)
f2(x)=1 (mod 3)
f3(x)=2 (mod 3)
f4(x)=0+X (mod 3)
f5(x)=1+X (mod 3)
f6(x)=2+X (mod 3)
f7(x)=0+2X (mod 3)
f8(x)=1+2X (mod 3)
f9(x)=2+2X (mod 3)
Each shareholder fj has (d0,fj(), d1,fj(0), d2,fj(1), d3,fj(2)). FIG. 1 concretely shows the sets of shares held in the individual shareholders. FIG. 2 shows combinations of shareholders and relevant share.
As shown in FIG. 1, for example when shareholders f1, f4, and f8 (second row) perform shared decryption, they extract the share corresponding to X=. Each of them can compute the output corresponding to the secret key d by doing calculations using (d0,0, d0,1, d0,2).
In FIG. 2, a combination with one of the alphabetic characters a to l means that there are three types of computation routes for the output corresponding to the secret key d in the same combination in each shareholder (in FIG. 2, xe2x80x9cdxe2x80x9d is merely an alphabetic character, not the secret key d). For example, in the combination (f1, f2, f3) with character b, it is possible to collect three shares to recover the secret key d using any of X=0, 1, and 2.
In connection with the (n, n) secret sharing scheme in reference [BF97], there is a scheme that has introduced the concept of threshold scheme (Y. Frankel, P. D. MacKenzie and M. Yung, xe2x80x9cRobust efficient shared RSA-key generation,xe2x80x9d Proceedings of the thirtieth annual ACM symposium on theory of computing, pp. 663-672, 1998, which is hereinafter referred to as [FMY98]).
In the scheme of reference [FMY98], a (t, n) key generation and sharing scheme based on the (n, n) secret sharing in reference [BF97] has been described. Specifically, (n, n) key generation is performed and then the sum of polynomials for the secret key d is obtained. Then, each shareholder Pi becomes a dealer for share di and performs Sum-to-Poly conversion (conversion of sum into polynomials). At this time, each shareholder Pi combines the pieces of shared information for the partial information dj from all the shareholder Pj and finally performs secret sharing of the secret key d, thereby realizing the (t, n) secret sharing of the secret key d.
As a result, in the scheme of reference [FMY98], any t shareholders P out of a total of n shareholders can compute the RSA secret key d and therefore recover the key.
The above-described secret sharing systems, however, have the following problems.
In the scheme of reference [BBDW96], since it is impossible to construct (t, lm) secret sharing when n greater than 32 for t=3 and when txe2x89xa74, a method of constructing (2, n) secret sharing has not been generalized.
In the scheme of reference [FMY98], the secret key d has not been computed and a problem has arisen in performing signature or decryption using the secret key d. For example, it is assumed that there is a ciphertext C=Me (mod N) encrypted using the public key (e, N). When any t shareholders (let a set of these shareholders be xcex9) decrypt the ciphertext C, each shareholder Pj must calculate Lagrange""s interpolation coefficient xcexj,xcex9 as shown in equation (6) and determine each partial output from the interpolation coefficient xcexj,xcex9.                               λ                      j            ,            Λ                          =                              ∏                          l              ∈                              Λ                ⁢                \                ⁢                                  {                  j                  }                                                              ⁢                                    l                              l                -                j                                      ⁢                          (                              mod                ⁢                                  xe2x80x83                                ⁢                                  φ                  ⁡                                      (                    N                    )                                                              )                                                          (        6        )            
However, since none of the shareholders know primary factors of composite number N (=pq), they cannot compute the multiplicative inverse elements of 1xe2x88x92j with the order xcfx86 (N) of the width as modulus and therefore cannot compute Lagrange""s interpolation coefficient xcexj,xcex9. Consequently, they cannot perform shared decryption to recover the plaintext by combining partial outputs as shown in equation (7).                                           ∏                          j              ∈              Λ                                ⁢                      C                                          s                j                            ·                              λ                                  j                  ,                  Λ                                                                    =                              C            d                    =                      M            ⁡                          (                              mod                ⁢                                  xe2x80x83                                ⁢                N                            )                                                          (        7        )            
It is, accordingly, an object of the present invention to provide a (t, n) secret sharing system and a storage medium which enable any t out of n shareholders to perform shared decryption and signature without computing a secret key in an environment where no dealer exists.
According to a first aspect of the present invention, there is provided a (t, n) secret sharing system which is used for a crypto system based on the problem of factorization into prime factors and, when partial final information about a secret key is shared to n shareholders and any of the n shareholders cannot calculate the secret key from its own partial final information, enables any t shareholders out of the n shareholders to create the result of decryption and the result of signature without computing the secret key.
According to a second aspect of the present invention, there is provided a (t, n) secret sharing system which is applied to an RSA crypto system using a public key and a secret key d and which includes n shareholders connected to each other via a network and a user unit and, when partial final information about the secret key d is shared to n shareholders, enables any t shareholders out of the n shareholders to create at least either the result of decryption or the result of signature without computing the secret key d, wherein each of the n shareholders comprises means for creating the public key and the secret key d, means for holding a piece of (n, n) share di (0xe2x89xa6ixe2x89xa6n) created on the basis of the secret key d, means for, if the smallest integer equal to or larger than the logarithm of n to the base t is r, turning the share di into t(r+1) partial random numbers of the (t, n) type and sharing r+1 out of the t(r+1) partial random numbers to the respective shareholders on the basis of a t-ary representation (value k at the tj-th digit, 0xe2x89xa6kxe2x89xa6txe2x88x921, 0xe2x89xa6jxe2x89xa6r) of the identification number of each of the shareholders, means for putting together n(r+1) partial random numbers shared by the shareholders for each digit tj in the t-ary representation and obtaining r+1 pieces of partial final information dj,k, means for performing an operation on the data to be processed received from the user unit on the basis of the partial final information dj,k and returning the obtained partial output to the user unit, and the user unit comprises means for selecting the t shareholders and transmitting data to be processed to the selected t shareholders, and means for combining the partial outputs received from the t shareholders and obtaining the result of decryption or the result of signature.
According to a third aspect of the present invention, there is provided a (t, n) secret sharing system which is applied to an RSA crypto system (the greatest common divisor of e and L2 is 1 and modulus N is common) using a first public key (e, N), a secret key d, and a second public key (L2, N) and which includes n shareholders connected to each other via a network and a user unit and, when share sj about the secret key d is shared to n shareholders, enables any t shareholders out of the n shareholders to create the result of decryption without computing the secret key d, wherein each of the n shareholders comprises means for performing an operation on data C2 (=Me (mod N)) to be decrypted received from the user unit to produce a partial output Zj and returning the partial output Zj to the user unit, and the user unit comprises means for selecting t shareholders out of the n shareholders and transmitting the data C2 to be decrypted to the selected t shareholders, means for combining the partial outputs Zj received from the t shareholders to obtain the result of decryption C1 (=ML{circumflex over ( )}2 (mod N) where {circumflex over ( )} represents power), and means for performing an operation on the basis of the result of decryption C1, the data to be decrypted C2, and the following equations to determine the result of final decryption M:
a1=(L2)xe2x88x921 (mod e)
xe2x80x83a2=(a1L2xe2x88x921)/e
M=C1a1 (C2a2)xe2x88x921 (mod N)
According to a fourth aspect of the present invention, there is provided a (t, n) secret sharing system which is applied to an RSA crypto system (the greatest common divisor of e and L2 is 1, modulus N is common, and L=(nxe2x88x921)!) using a first public key (e, N), a secret key d, and a second public key (L2, N) and which includes n shareholders connected to each other via a network and a user unit and, when share sj about the secret key d is shared to n shareholders, enables any t shareholders out of the n shareholders to create the result of signature without computing the secret key d, wherein each of the n shareholders comprises means for performing an operation on data S2 (=M) to be signed received from the user unit to produce a partial output Zj and returning the partial output Zj to the user unit, and the user unit comprises means for selecting t shareholders out of the n shareholders and transmitting the data S2 (=M) to be signed to the selected t shareholders, means for combining the partial outputs Zj received from the t shareholders to obtain the result of signature S1 (=MdL{circumflex over ( )}2 (mod N) where {circumflex over ( )} represents power), and means for performing an operation on the basis of the result of signature S1 (=(Md)e), the data to be signed S2 (=(Md)L{circumflex over ( )}2), and the following equations to determine the result of final signature Md:
a1=(L2)xe2x88x921 (mod e)
a2=(a1L2xe2x88x921)/e
Md=S1a1 (S2a2)xe2x88x921 (mod N)
With the configurations according to the first and second aspects of the present invention, each of the n shareholders creates the public key and the secret key d and holds a piece of (n, n) share di (0xe2x89xa6ixe2x89xa6n) created on the basis of the secret key d. If the smallest integer equal to or larger than the logarithm of n to the base t is r, each of the n shareholders turns the share di into t(r+1) partial random numbers of the (t, n) type, shares r+1 out of the t(r+1) partial random numbers to the respective shareholders on the basis of a t-ary representation (value k at the tj-th digit, 0xe2x89xa6kxe2x89xa6txe2x88x921, 0xe2x89xa6jxe2x89xa6r) of the identification number of each of the shareholders, and puts together n(r+1) partial random numbers shared by the shareholders for each digit tj in the t-ary representation to obtain r+1 pieces of partial final information dj,k.
Then, the user unit selects the t shareholders and transmits data to be processed to the selected t shareholders. The t shareholders perform an operation on the data to be processed received from the user unit on the basis of the partial final information dj,k and returns the obtained partial outputs to the user unit. Then, the user unit combines the partial outputs received from the t shareholders to obtain the result of decryption or the result of signature.
As described above, any t shareholders out of the n shareholders can perform shared decryption or signature without computing the secret key in an environment where there is no dealer. In addition, high processing efficiency can be realized without using Lagrange""s interpolation.
Furthermore, with the configuration according to the third aspect of the present invention, in an RSA crypto system (the greatest common divisor of e and L2 is 1 and modulus N is common) using a first public key (e, N), a secret key d, and a second public key (L2, N), when share sj about the secret key d is shared to n shareholders, a user unit selects t from the n shareholders and transmits data to be decrypted C2 to the selected t shareholders. Each of the t shareholders performs an operation on data C2 (=Me (mod N)) to be decrypted received from the user unit to produce a partial output Zj and returns the partial output Zj to the user unit. The user unit combines the partial outputs Zj received from the t shareholders to obtain the result of decryption C1 (=ML{circumflex over ( )}2 (mod N)) and performs an operation on the basis of the result of decryption C1, the data to be decrypted C2, and the specific equations (a1=(L2)xe2x88x921 (mod e), a2=(a1L2xe2x88x921)/e, M=C1a1(C2a2)xe2x88x921 (mod N)) to determine the result of final decryption M.
As described above, any t shareholders out of the n shareholders can perform shared decryption without computing the secret key in an environment where there is no dealer. In addition, high processing efficiency can be realized on the basis of Lagrange""s interpolation using a public key under specific conditions.
Still furthermore, with the configuration according to the fourth aspect of the present invention, data to be signed S2 (=M) is used in place of data C2 to be decrypted and the result of signature S1 (=MdL{circumflex over ( )}2 (mod N) where {circumflex over ( )} represents power) is used in place of the result of decryption C1. Instead of means for determining the result of final description M, an operation is performed on the basis of the result of signature S1 (=(Md)e), the data to be signed S2 (=(Md)L{circumflex over ( )}2), and specific equations (a1=(L2)xe2x88x921 (mod e), a2=(a1L2xe2x88x921)/e, Md=S1a1(S2a2)xe2x88x921 (mod N)) to determine the result of final signature Md.
As a result, the signature process can realize a similar operation to that of the third aspect.
Additional objects and advantages of the invention will be set forth in the description which follows, and in part will be obvious from the description, or may be learned by practice of the invention. The objects and advantages of the invention may be realized and obtained by means of the instrumentalities and combinations particularly pointed out hereinafter.